/*
Input: V, E, s

//Initialization
for each v from V
	dist[v] = infinity
	prev[v] = null
	add v to Q

While Q not empty:
	u <- remove_min(Q)
	
	[Optional: 
	if (u == dest) 
		return dist, prev]
	
	for each neighbor w of u
		if dist(u) + (u,w) < dist(w) then
			dist(w) = dist(u) + (u,w)
			prev(w) = u	
	
	return dist, prev
*/

struct Vertex {
	Vertex(std::string strName) : name(strName), edges(std::vector<Edge*>()) {}
	std::string name;
	std::vector<Edge*> edges; 	//combined with Edge.indexA and Edge.indexB
								// this provides O(1) lookup
};

struct Edge {
	Edge(const Vertex& vA, const Vertex& vB, nDist, int iA, int iB, int d) 
	: a(vA), b(vB), indexA(iA), indexB(iB), dist(d) 
	{}
	
	Vertex &a;
	Vertex &b;
	int indexA;
	int indexB;
	int dist;
};

Vertex v1("1");
Vertex v2("2");
Vertex v3("3");
Vertex v4("4");
Vertex v5("5");
Vertex v6("6");

Edge e12(v1, v2, 0, 0, 7);
Edge e13(v1, v3, 0, 0, 9);
Edge e16(v1, v6, 0, 0, 14); // 14

Edge e24(v2, v4, 0, 0, 15); // 15
Edge e23(v2, v3, 0, 0, 10); // 10

Edge e34(v3, v4, 0, 0, 11); // 11
Edge e36(v3, v6, 0, 0, 2); // 2

Edge e45(v4, v5, 0, 0, 6); // 6

Edge e56(v5, v6, 0, 0, 9); // 9

std::vector<Vertex> V;

std::vector<Edge &> dijkstra(const Vertex& vSrc, std::vector<Vertex> V)
{
	std::vector<Edge&> SP;
	
	
	
}